package org.example.leetcode;

import org.example.yuewen.solution23.ReverseListNode;

import java.util.Stack;

/**
 * @author: lynn
 * @Descript: 两个链表相加，注意和是向后加
 * @date: 2021/7/11 9:08
 * @version: 1.0
 *
 *  https://www.bilibili.com/video/BV19T4y1j7qJ?from=search&seid=1286284479343927718&spm_id_from=333.337.0.0
 */
public class LC2 {
    public static void main(String[] args) {
        ListNode l1=new ListNode(2);
        l1.next=new ListNode(4);
        l1.next.next=new ListNode(9);

        ListNode l2=new ListNode(5);
        l2.next=new ListNode(6);
        l2.next.next=new ListNode(4);
        l2.next.next.next=new ListNode(9);
        ListNode l3=plusTwoListNode(l1,l2);
        System.out.println("xxxx");
    }

    /**
     * 头插法，需要翻转
     */
    private static ListNode plusTwoListNode(ListNode l1,ListNode l2){
        ListNode  dummy=new ListNode(0);//哑节点
        Stack<Integer> s1=new Stack<>();
        Stack<Integer> s2=new Stack<>();
        int carryBin=0;
        while (l1!=null){
            s1.push(l1.val);
            l1=l1.next;
        }
        while (l2!=null){
            s2.push(l2.val);
            l2=l2.next;
        }
        while (s1.size()!=0 || s2.size()!=0 || carryBin !=0){
            int tmp1=0; int tmp2=0;
            tmp1=s1.size()>0?s1.pop():0; //fixme 要考虑清0，否则 就算某个stack为0，其他的还能当做末尾用，lc339
            tmp2=s1.size()>0?s1.pop():0;
            int mod=(tmp1+tmp2+carryBin)%10;
            carryBin=(tmp1+tmp2+carryBin)/10;
            //头插法 保持newNode 永远在 dummy.next的前面
            //      dummy(a1)        dummy.next(a1.next)
            //           newNode(s)

            ListNode newNode=new ListNode(mod);
            //将新节点连接到dummy链表的头部
            newNode.next=dummy.next;
            //header永远存储第一个节点的地址
            dummy.next=newNode;

            //while 第一次 经过一顿操作后变成 dummy newNode
            //while 第二次 经过一顿操作后变成 dummy newNode newNode
        }
        return reverseNode(dummy.next);
    }

    private static ListNode reverseNode(ListNode head){
        if (head==null||head.next==null){
            return head;
        }

        ListNode preNode =null;
        ListNode curNode=head;
        while (curNode!=null){
            ListNode nextNode=curNode.next;
            curNode.next=preNode;
            preNode=curNode;
            curNode=nextNode;
        }
        return preNode;
    }

    /*public static ListNode plusTwoListNode(ListNode l1,ListNode l2){
        int carryBin=0;
        Stack<Integer> stack1=new Stack<>();
        Stack<Integer> stack2=new Stack<>();
        while (l1!=null){
            stack1.push(l1.val);
            l1=l1.next;
        }
        while (l2!=null){
            stack2.push(l2.val);
            l2=l2.next;
        }
        ListNode dummyHead=new ListNode(0);
        ListNode tail=dummyHead;

        while (stack1.size()!=0 || stack2.size()!=0 ||carryBin!=0){
            int tmp1=0;int tmp2=0;
            if (stack1.size()!=0) tmp1=stack1.pop();
            if (stack2.size()!=0) tmp2=stack2.pop();
            int mod=(tmp1+tmp2+carryBin)%10;
            carryBin=(tmp1+tmp2+carryBin)/10;
            ListNode newNode=new ListNode(mod);
            tail.next=newNode;
            tail=newNode;
        }
        return dummyHead.next;
    }*/


    private static  class ListNode{
        ListNode next;
        int val;
        ListNode(int val){
            this.val=val;
        }
    }
}
